package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 2233. K 次增加后的最大乘积
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/15 10:31
 */
public class MaximumProduct {

    public static void main(String[] args) {
        MaximumProduct test = new MaximumProduct();

        // 输入：nums = [0,4], k = 5
        //输出：20
        //解释：将第一个数增加 5 次。
        //得到 nums = [5, 4] ，乘积为 5 * 4 = 20 。
        //可以证明 20 是能得到的最大乘积，所以我们返回 20 。
        //存在其他增加 nums 的方法，也能得到最大乘积。
        //示例 2：
        //
        //输入：nums = [6,3,3,2], k = 2
        //输出：216
        //
        //来源：力扣（LeetCode）
        //链接：https://leetcode-cn.com/problems/maximum-product-after-k-increments
        //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

        // 20
//        int[] arr = {0,4};
//        int k = 5;

        // 216
//        int[] arr = {6,3,3,2};
//        int k = 2;

        // 1
//        int[] arr = {0};
//        int k = 1;

        // 2
        int[] arr = {1, 1};
        int k = 1;

        int i = test.maximumProduct(arr, k);
        System.out.println(i);
    }

    public int maximumProduct(int[] nums, int k) {
        long st = 0;
        long end = Integer.MAX_VALUE;
        long t = 0;
        long m = 0;
        while (st <= end) {
            t = 0;
            m = st + ((end - st + 1) >> 1);
            for (int num : nums) {
                if (num < m) {
                    t += (m - num);
                }
            }
            if (t == k) {
                break;
            }
            if (t < k) {
                if (st == end) {
                    break;
                }
                st = m;
            } else {
                end = m - 1;
            }
        }
        t = k - t;
        long sum = 1L;
        for (int num : nums) {
            if (num <= m) {
                num = (int) m;
                if (t > 0) {
                    t--;
                    num++;
                }
            }
            sum = sum * num % 1000000007;
        }
        return (int) sum;
    }

}
